package com.zlk.algorithm.huawei.leetcode.unionAndFind;

import org.junit.Test;

import java.util.Stack;

/**
 * @program: algorithm
 * @ClassName Code59_FriendCircles
 * @description: https://leetcode.cn/problems/friend-circles/
 *
 *
 * 有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，
 * 且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
 * 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
 * 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1
 * 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
 *
 * 返回矩阵中 省份 的数量。
 *
 * 输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
 * 输出：2
 *  连通图解题模板
 * @author: slfang
 * @create: 2025-01-20 17:05
 * @Version 1.0
 **/
public class Code59_FriendCircles {


    @Test
    public void test(){
       int[][] martix = new int[][]{{1,1,0},{1,1,0},{0,0,1}};
       System.out.println(findCircleNum(martix));
    }

    //  1   1   0
    //  1   1   0
    //  0   0   1
    //
    public int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        int m = isConnected[0].length;
        UnionAndFind unionAndFind = new UnionAndFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <i ; j++) {
                if(isConnected[i][j]==1){
                    unionAndFind.union(i,j);
                }
            }
        }
        return unionAndFind.getSets();
    }


    class UnionAndFind{
        int[] size;
        int[] father;

        int[] help ;
        int sets;

        public int getSets(){
            return sets;
        }

        public UnionAndFind(int n){
            father=new int[n];
            size=new int[n];
            help = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
                size[i]=1;
            }
            sets = n;
        }

        //查找父节点
        public int findFather(int cur){
            Stack<Integer> stack = new Stack<>();
            while (father[cur]!=cur){
                stack.add(cur);
                cur = father[cur];
            }
            while (!stack.isEmpty()){
                father[stack.pop()] = cur;
            }
            return cur;
        }
        public int findFather1(int cur){
            int i=0;
            while (father[cur]!=cur){
                help[i++] = cur;
                cur = father[cur];
            }
            i--;
            while (i>=0){
                father[help[i--]] = cur;
            }
            return cur;
        }

        //两个节点是否相连
        public boolean isConnect(int a,int b){
            return findFather(a)==findFather(b);
        }

        public void union(int a,int b){
            int fatherA = findFather(a);
            int fatherB = findFather(b);
            if(!isConnect(fatherA ,fatherB)){
                int sizeA = size[fatherA];
                int sizeB = size[fatherB];
                if(sizeA>sizeB){
                    father[fatherB] = fatherA;
                    sizeA +=sizeB;
                }else{
                    father[fatherA] = fatherB;
                    sizeB+=sizeA;
                }
                sets--;
            }
        }

    }

}
